﻿//#define LEVEL
using System;
using System.Collections.Generic;
using System.ComponentModel;
using System.Diagnostics;
using System.Linq;

using alib.BitArray;
using alib.Collections;
using alib.Concurrency;
using alib.Enumerable;

namespace agree
{
	///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
	/// <summary>
	/// 
	/// </summary>
	///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
	public abstract partial class LatticeType : Instance
	{
		public LatticeType(Grammar g, String name)
			: base(g.td, g, name)
		{
		}
#if LEVEL
		public int m_level;
#endif
		public int bit_num;
		public BitArr bit_vec;

		/// <summary>
		/// Immediate parents only. Does not include this node
		/// </summary>
		[DebuggerBrowsable(DebuggerBrowsableState.Never)]
		public HashSet<Type> parents = new HashSet<Type>();

#if LEVEL
		public int FindLevel()
		{
			if (m_level == 0 && this != tm.TopType)
				m_level = i_parents.Max(p => p.FindLevel()) + 1;
			return m_level;
		}
#endif

		[DebuggerBrowsable(DebuggerBrowsableState.Never)]
		public int c_children;

		/// <summary>
		/// leaf types have no children. They may have appropriate features
		/// </summary>
		[DebuggerBrowsable(DebuggerBrowsableState.Never)]
		public bool IsLeaf { get { return c_children == 0; } }

		internal void _set_has_features_below()
		{
			m_flags |= Flags.FeaturesBelow;
			foreach (Type p in parents)
				if (!p.HasFeaturesBelow)
					p._set_has_features_below();
		}

		///////////////////////////////////////////////////////////////////////////////////////////////////////////////////
		/// if a parent has zero or one child, then taking a node away would make it a leaf,
		/// which should never happen when calculating GLBs.
		///////////////////////////////////////////////////////////////////////////////////////////////////////////////////
		bool _redundant_with_parent(Type par)
		{
			if (par.bit_vec.OnesCount <= bit_vec.OnesCount)
				return false;
			if (!parents.Contains(par))
				return false;
			par.c_children--;
			return true;
		}

		///////////////////////////////////////////////////////////////////////////////////////////////////////////////////
		///
		///////////////////////////////////////////////////////////////////////////////////////////////////////////////////
		public void SwitchParentTo(Type par)
		{
			parents.RemoveWhere(par._redundant_with_parent);
			parents.Add(par);
			par.c_children++;
		}

		public void AddParent(Type par)
		{
			if (!parents.Add(par))
			{
				//SysObj.Instance.TransactionStatus(bcpo, "warning: type '{0}' already has parent '{1}'", this.Name, par.Name);
				return;
			}
			par.c_children++;
		}

		/// <summary>
		/// Immediate non-GLB parents; GLB parents resolved to non-GLBs.
		/// </summary>
		[DebuggerBrowsable(DebuggerBrowsableState.Never)]
		public IEnumerable<Type> NonGlbParents
		{
			get
			{
				HashSet<Type> hs = new HashSet<Type>();
				_find_non_glb_parents(hs);
				hs.RemoveWhere(t => t.AllDescendants.Any(pc => hs.Contains(pc)));
				return hs;
			}
		}
		public void _find_non_glb_parents(HashSet<Type> hs)
		{
			foreach (var p in parents)
				if (p.IsGlb)
					p._find_non_glb_parents(hs);
				else
					hs.Add(p);
		}

		/// <summary> Immediate children only. Does not include this node </summary>
		Type[] children = null;
		[DebuggerBrowsable(DebuggerBrowsableState.Never)]
		public Type[] Children
		{
			get
			{
				if (children == null)
				{
					if (bcpo.type_arr != null)
						render_all_children(bcpo.type_arr);
					else
						render_all_children2(bcpo);
				}
				return children;
			}
		}

		/// <summary>
		/// Reverse all parent pointers to create all 'immediate children' sets. The latter are now
		/// no longer operationally necessary, but may be demanded by vizualizers or editing tools etc.
		/// The operation is O(N) vs O(N^2) if the whole graph is done all at once, as opposed
		/// to one type at a time, so we do the whole graph the first time a list is requested.
		/// </summary>
		static void render_all_children(Type[] src)
		{
			Debug.Assert(src[0] == src[0].td.ΔTop);
			List<Type>[] rgrg = new List<Type>[src.Length];
			Type c;
			for (int i = configuration.TypesConfig.TopId + 1; i < src.Length; i++)
				foreach (var p in (c = src[i]).parents)
					(rgrg[p._id] ?? (rgrg[p._id] = new List<Type>())).Add(c);
			for (int i = configuration.TypesConfig.TopId; i < rgrg.Length; i++)
			{
				var rg = rgrg[i];
				src[i].children = rg == null ? Collection<Type>.None : rg.ToArray();
			}
		}
		/// version used when tm.type_arr isn't initialized yet
		static void render_all_children2(_ICollection<Type> src)
		{
			Dictionary<Type, List<Type>> dict = new Dictionary<Type, List<Type>>();
			foreach (var c in src)
			{
				c.children = null;
				foreach (var p in c.parents)
				{
					List<Type> lt;
					if (!dict.TryGetValue(p, out lt))
						dict.Add(p, lt = new List<Type>());
					lt.Add(c);
				}
			}
			foreach (var kvp in dict)
				kvp.Key.children = kvp.Value.ToArray();
		}

		/// <summary>
		/// Immediate non-GLB children; GLB parents resolved to non-GLBs.
		/// </summary>
		[DebuggerBrowsable(DebuggerBrowsableState.Never)] // side-effect: renders child links
		public IEnumerable<Type> NonGlbChildren
		{
			get
			{
				HashSet<Type> hs = new HashSet<Type>();
				_find_non_glb_children(hs);
				hs.RemoveWhere(t => t.AllAncestors.Any(cp => hs.Contains(cp)));
				return hs;
			}
		}
		void _find_non_glb_children(HashSet<Type> hs)
		{
			foreach (var c in Children)
				if (c.IsGlb)
					c._find_non_glb_children(hs);
				else
					hs.Add(c);
		}

		void _gather_ancestors(HashSet<Type> hs)
		{
			foreach (Type t in parents)
				if (hs.Add(t))
					t._gather_ancestors(hs);
		}

		/// <summary>
		/// does not include this type itself
		/// </summary>
		public HashSet<Type> AllAncestors
		{
			get
			{
				HashSet<Type> hs = new HashSet<Type>();
				_gather_ancestors(hs);
				return hs;
			}
		}

		public HashSet<Type> AllAncestorsInclusive
		{
			get
			{
				HashSet<Type> hs = AllAncestors;
				hs.Add((Type)this);
				return hs;
			}
		}

		/// <summary>
		/// does not include this type itself
		/// </summary>
		[DebuggerBrowsable(DebuggerBrowsableState.Never)] // side-effect: renders child links
		public HashSet<Type> AllDescendants
		{
			get
			{
				HashSet<Type> hs = new HashSet<Type>();
				_walk_children(hs);
				return hs;
			}
		}

		[DebuggerBrowsable(DebuggerBrowsableState.Never)] // side-effect: renders child links
		public HashSet<Type> AllDescendantsInclusive
		{
			get
			{
				HashSet<Type> hs = new HashSet<Type>();
				hs.Add((Type)this);
				_walk_children(hs);
				return hs;
			}
		}

		void _walk_children(HashSet<Type> hs)
		{
			foreach (Type t in Children)
				if (hs.Add(t))
					t._walk_children(hs);
		}

		/// <summary> (or equal) </summary>
		public bool IsSubsumedBy(Type t)
		{
			return this == t || bit_vec.OnesCount == 1 ? t.bit_vec[bit_num] : bit_vec.IsSubsumedBy(t.bit_vec);
		}
		/// <summary> (or equal) </summary>
		public bool Subsumes(Type t)
		{
			return t == this || t.bit_vec.OnesCount == 1 ? bit_vec[t.bit_num] : t.bit_vec.IsSubsumedBy(bit_vec);
		}

		///////////////////////////////////////////////////////////////////////////////////////////////////////////////////
		///
		/// following functions used by lattice BCPO and closure
		/// 
		///////////////////////////////////////////////////////////////////////////////////////////////////////////////////

		/// <summary>
		/// set the specified bitarray index 'baix' in this type's code and the codes of and 
		/// all of its ancestors. After applying to the whole graph, the number of set bits in 
		/// each type's code is its number of descendant types (+1 for itself)
		/// </summary>
		internal void _mark_ancestor_bit_codes(int code_size, int ix)
		{
			if (bit_vec == null)
			{
				(bit_vec = new BitArr(code_size))[ix] = true;
				bit_num = -2;
			}
			else if (!bit_vec.TrySet(ix))
				return;
			foreach (Type t in parents)
				if (!t.IsTop)
					t._mark_ancestor_bit_codes(code_size, ix);
		}

		internal void _set_parent_descendant_bits(BitArr code)
		{
			foreach (Type p in parents)
				if (!p.IsTop)
					p.reset_code_for_2nd_pass().OrEq(code);
		}

		/// <summary>
		/// reset the type's code if this is its first appearance in the final pass
		/// </summary>
		internal BitArr reset_code_for_2nd_pass()
		{
			if (bit_num == -2)
			{
				bit_vec.ClearAll();
				bit_num = -1;
			}
			return bit_vec;
		}

		///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
		/// Type-to-type comparisons
		///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////

		public static new class Compare
		{
			public static class DescendantCount
			{
				public static readonly IComparer<Type> Forward = new _fwd();
				public static readonly IComparer<Type> Reverse = new _rev();
				public sealed class _fwd : IComparer<Type>
				{
					public int Compare(Type x, Type y)
					{
						Debug.Assert(x != y);
						int d;
						return (d = x.bit_vec.OnesCount - y.bit_vec.OnesCount) != 0 ? d : y._id - x._id;
					}
				};
				public sealed class _rev : IComparer<Type>
				{
					public int Compare(Type x, Type y)
					{
						Debug.Assert(x != y);
						int d;
						return (d = y.bit_vec.OnesCount - x.bit_vec.OnesCount) != 0 ? d : x._id - y._id;
					}
				};
			};
		};
	};
}
